HW#2 --- last modified February 28 2019 22:22:59..

Solution set.

Due date: Mar 16

Files to be submitted:
  Hw2.zip

Purpose: To learn about direct linked networks by writing a simulator for Ethernet and the Sliding Window Protocol.

Related Course Outcomes:

The main course outcomes covered by this assignment are:

LO1 -- Understand layered architectures.

LO3 -- Analyze the performance metrics of networks, including bandwidth, delay, and error rate.

LO4 -- Describe local area network protocols including Ethernet, Token Ring, and Wireless LAN, and their major schemes such as Spanning Tree Protocol (STP) in IEEE 802.1D.

LO5 -- Develop a software simulator for local area network protocols.

Specification:

As with Hw1, there are two parts to this assignment: (1) A written part which should be put in your submitted ZIP file in the file Hw2.pdf. For this part I want you to do any four out of the following eight problems out of the text: Chapter 2: 8, 13, 18, 31, 41, 55, 61. Chapter 3: 1 . The file Hw2.pdf should clearly indicate all group members in this file. (2) A Java network simulator, which will be described below.

Your Java network simulator will be used to simulate the three layers of a network we have seen so far: the Physical Layer, the Media Access Control sublayer (corresponding to Ethernet), and the logical link sublayer (handling acknowledgments and flow control in our case). The later two layers are commonly distinguished sublayers of the data link layer. The main class for your project should be the class NetworkSimulator. After compiling your simulator, one should be able to test it out by typing the command:

java NetworkSimulator similator_data num_steps

Your program should then read in the contents of the file simulator_data and begin executing the network simulation for a total of num_steps. The simulator_data file format consists of a sequence of configuration of hosts, together with timings for various host actions:

***
mac_address_1
SWS:RWS
Delay
Timer_Initial_Value
2;a1:b2:c3:d9:e4:f5;blah blah Blah
10;e1:f2:c3:d9:e4:f5;yummy packet...
12;a1:2:d3:d9:e4:f5;more stuff
***
mac_address_2
SWS2:RWS2
Delay2
Timer_Initial_Value2
...
***
...
***

For this project you will create several such simulator_data files for the different experiments I will ask you to perform. The data between each pair of ***'s represents one particular host on the network. The first line indicates the name of the host. This is given as a hexadecimal mac address. The next line indicates the send and receive window size of the particular host. These should be integers separated by a colon. Delay is an integer which indicates the line delay between the machine and the Hub. Timer_Initial_Value is an integer which represents the initial value of a timer that the host as a sender uses for a frame in its sending window. Each subsequent line is an instruction to send a frame. It consists of a number followed by a semicolon followed by a destination MAC address, followed by a semicolon, followed by the contents of the frame. To keep things simple the contents of the frame only go to the next newline character. Numbers represent time steps from the start of the simulation. So "2;a1:b2:c3:d9:e4:f5;blah blah blah" means wait two time steps from the start of the simulation then the given host receives "blah blah blah" into its send buffer which it wants to transmit in a frame as soon as possible to destination a1:b2:c3:d9:e4:f5.

The NetworkSimulator class should have a field simulatorStep which counts up from 0 to num_steps in a for loop. Each iteration, this function calls the NetworkSimulator's update(curStep) method. In addition to the NetworkSimulator class, you should also have a Host class, a MACLayer class, a Wire class, and a Hub class. After calling the NetworkSimulator's update(curStep) method, the for loop should then can the Hub's update() method. We will describe this more towards the end of the homework description. The NetworkSimulator should have one instance of Host for each host specified in the simulator_data file. Each Host class should have access to a MACLayer object. Each MACLayer object should have access to a Wire object. Each Wire object should be connected to the Singleton Hub object. When update(curStep) is called, the NetworkSimulator class checks for each Host specified in the simulator_data file whether there was action in simulator_data for it. If there was, it calls the given Host's sendtoHost(MacAddress destinationMac, String sendData) method. This method should print to standard out when it is called a string like:

Host:srcMac buffers sendData to send to destinationMac

sendToHost should then construct a SimulatorFrame object and put this on the queue for the given Host (you can choose whichever Java collection class you want to implement the queue).

Besides checking for actions from the simulator_data file, for each Host, at each step, the NetworkSimulator should call that Host's update() method. The first thing a Host's update() method should do is call its MACLayer object's update() method. If should then call the MACLayer object's status() method. This might return either the value "BUSY" or "IDLE". If it returns "BUSY", then the Host's update() method is done for this step. Otherwise, this method should then call the MACLayer's getFrame() method. This returns null if there hasn't been a SimulatorFrame received since the last time step. Otherwise, it returns a received SimulatorFrame. A SimulatorFrame should have a frameType field, an int sequenceNumber field, a MACAddress destinationMAC, a MACAddress senderAddress, and a String frameData field. On receipt of such a frame, the update method should print to standard out:

Host destinationMac received frame from senderAddress of type frameType, sequence number sequenceNumber, and data frameData.

After printing this out, the Host's update method should check the frameType, if the frameType is "DATA" or "RESENT_DATA", the sequenceNumber is checked and the appropriate ACK SimulatorFrame should be created (if needed) and added put on the queue of frames to send. The Host should also maintain a window of received frames of size RWS mentioned above, and should appropriately add the SimulatorFrame to this window. The Frame is discarded if there is no room left in the window. If a frame in the receiver window has had an ACK SimulatorFrame sent which would acknowledge its receipt, then it should be discarded from the window. The line:

Frame from senderAddress of type frameType, sequence number sequenceNumber, and data frameData has now been acknowledged

should be printed. At the point the Host's update() method, begins to execute the sender protocol for sliding window. First, if rather than type "DATA" or "RESENT_DATA", the frameType had been "ACK", then the sender sliding window protocol would be updated accordingly. The sender stage then updates the timers (decrements by 1) on each of the frames that are in the sender's window. If a timer gets to 0, that frame is re-added to send queue, but with frameType "RESENT_DATA". Its timer is then reset. The sender stage then checks to see if there are any "ACK" frames or "RESENT_DATA" frames that need to be sent on the queue buffering frames to be sent. If there are, it flips a coin. If the coin lands heads, it sends the next acknowledgment or resent data frame that needs to be sent. It uses its MACLayer object's sendFrame(SimulatorFrame frame) method to do this. This would terminate the Host update() method. If it lands tails, or if there are no ACK frames or RESENT_DATA frames to send, then the host checks if there is space in its sending window. If so, it checks for frames in the queue to add to the sender window. When it adds a frame to the sender window it also calls its MACLayer object's sendFrame(SimulatorFrame frame) to send this frame. After doing this, the Host's update method is done.

We next describe how a MACLayer object's update() method works. It first calls its Wire object's update() method. Then it calls the Wire's status() method. This might return either "DATA ON LINE", "IDLE", or "COLLISION". The MACLayer object's update() method then checks its currentOperation field. If this has the value "IDLE" and Wire's status was not "DATA ON LINE", the update method should return. If currentOperation has the value "SENDING" and the status was "IDLE", the update() method should read the next char of the outgoingFrameAsString field and call its Wire object's sendOutgoingChar(nextChar, flag) method. The variable flag can be one of "STARTFRAME", "ENDFRAME", "NORMAL" depending on which kind of character within the frame nextChar is. If nextChar was the last character of the frame, then the currentOperation is set to "IDLE" and update completes. If currentOperation has the value "SENDING" and the status was "COLLISION", then the currentOperation is set to "WAITING" and the nextChar is reset to the beginning of the frame. A counter is started with the number of steps to wait according to the exponential back-off algorithm. If the currentOperation is "WAITING" and the counter is greater than zero, the counter is decremented. If the currentOperation is "WAITING" and the counter is 0, the the currentOperation is set to "SENDING". If the currentOperation is either "SENDING","WAITING", or "IDLE" and the Wire's status was "DATA ON LINE", the update() method calls its Wire's receiveIncomingChar(); to read the next character of a frame. Wire should support isStartFrame() and isEndFrame() methods to check what kind of character this is. Characters should be read into an array and an index variable should keep track of which character of the frame was the last received. If isStartFrame() is true, this is reset to 0, a frameReady field is also set to false. If isEndFrame() is true, then a frameReady field should be set to true. This completes the description of the MACLayer's update() method.

We next describe a little more about some of the other methods of the MACLayer: The MACLayer getFrame() method checks the frameReady field and only returns the contents of this array if this is true and the destinationAddress of the frame matches the MACLayer objects address. The MACLayer status() method checks currentOperation and returns "BUSY" if currentOperation is either "SENDING" or "WAITING". Otherwise, it returns "IDLE". I am writing things in double quote like "IDLE" you can choose to implement these using either Strings or enums. The MACLayer sendFrame(SimulatorFrame frame) method converts the frame to a String (maybe do this by overriding the toString() method of SimulatorFrame) and sets this into the field outgoingFrameAsString. The format should use 1 char for frame type, 4 char's for the sequenceNumber, 6 char's destination MAC address, 6 char's source MAC address, and the remaining char's for data.

As various methods of the MACLayer are called you should also print out informative messages to standard out; however, I will leave the precise description and frequency of these messages to your discretion.

We now describe how the Wire class works. It has two arrays of the same length FrameData elements receivingLine and sendingLine. The length of the arrays should come from the value of Delay for the given Host in the simulator_data file. A FrameData element consists of one char to hold a field called data and one DataType type which can be one of "STARTFRAME", "ENDFRAME", "NORMAL", "IDLE", or "COLLISION". The update() method first performs a check of the two arrays to see if there are any "COLLISION"s. To do this, it scans along both the receivingLine and sendingLine and checks if the ith element of both is not "IDLE". If this is the case, then the type of both FrameData elements is set to "COLLISION". Next the update() method shifts the contents of the elements of the sendingLine over by 1. So the i+1st element gets the contents of the ith element. The contents of the 0th element is a FrameData element with data equal to '\0' and type equal to IDLE. The length-1 element is used as follows before it gets overriden: we call Hub hub = Hub.getInstance(), to get the Hub Singleton. Then we call hub.setFrameData(sendingLine[sendingLine.length -1], macAddress); Here macAddress is the macAddress of the Host connected to the Wire. setFrameData checks if the Hub's frameData Field is IDLE, if it is, it copies the passed data into frameData. If it is not "IDLE", its type field is set to "COLLISION". After sliding the sendingLine over by one, and after handling the Hub as mentioned above, the Wire's update method performs a second check of the two arrays to see if there are any "COLLISION"s. Next, the Wire's update() method, moves the receivingLine over by 1. In this case, the ith element is shifted to be the i-1th element. The length-1 element is set to be a FrameData element with data equal to '\0' and type equal to "IDLE". The old 0th element is discarded. After performing these operations, the update() method is done. The point of these shifting is of course to pretend that we have electrical signal propagating down wires.

Besides update(), Wire has four other important methods (we've already mentioned isStartFrame() and isEndFrame(), but these are minor): receiveIncomingChar(), sendOutgoingChar(nextChar, flag), sendIncomingFrameData(FrameData data), and status. The first reads the character contents of the 0th element of the receivingLine. The second sets the contents of the 0th FrameData element of sendingLine. sendIncomingFrameData sets the contents of the length-1 element of the receivingLine. Finally, status looks at the type field of the 0th element of the receivingLine. If it has value "COLLISION", then "COLLISION" is returned. If the receiving line has value "STARTFRAME", "ENDFRAME", "NORMAL" then the value should be "DATA_ON_LINE". Otherwise, "IDLE" is returned.

To complete the description of how the simulator works, we lastly describe the Hub's update() method, which was first mentioned when we described the NetworkSimulator's for loop. The Hub Singleton should have a list of all the Wire objects present in the simulator. When the Hub is first instantiated, the frameData field of the Hub had type "IDLE". In a given iteration of the NetworkSimulator's for loop this value may or may not be changed when a given Wire's update() method is called. Regardless, when the Hub's update() method is called it cycles over all the Wire's other than the one that set the frameData, calling their sendIncomingFrameData(frameData). If frameData's type was "COLLISION", then all Wires get their sendIncomingFrameData(frameData) called. Once this is completed frameData has its data set equal to '\0' and has its type set equal to "IDLE".

I have not spoken about the constructors for the classes above, so I've leave their precise description to you. Once you have the NetworkSimulator is working I want you to do some experiments with it. You should create simulator_data files stop_and_wait.txt, big_sender_receiver1.txt, big_sender_big_receiver.txt in order to test the effects on bandwidth of using stop and wait versus a big sender window but receiver window of size 1 versus a big sender and big receiver window. Next create some test files to test the exponential back-off algorithm: exp1.txt, exp2.txt, etc. Write up all of these experiments in the file experiments.txt.

The maximum group size for this project is four. Use your time wisely. Have a strategy of what each teammate is to do. Make sure to check up on the progress of your group mates. Use IRC or instant messaging to keep tabs on each other or have meetings.

Point Breakdown